package org.huawei260.TiKu.ODsuanfa;

import java.util.Arrays;
import java.util.Scanner;
public class D_2024D_4500__最小生成树5G网络建设 { 

//	public class Main {
		// 边
		static class Edge {
			int from; // 边起点
			int to; // 边终点
			int weight; // 边权重

			public Edge(int from, int to, int weight) {
				this.from = from;
				this.to = to;
				this.weight = weight;
			}
		}

		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);

			int n = sc.nextInt(); // 基站数量（节点数）
			int m = sc.nextInt(); // 基站对数量（边数）

			Edge[] edges = new Edge[m];

			for (int i = 0; i < m; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				int z = sc.nextInt();
				int p = sc.nextInt();

				// 如果p==1，则可以认为x-y边权为0
				edges[i] = new Edge(x, y, p == 0 ? z : 0);
			}

			System.out.println(kruskal(edges, n));
		}

		public static int kruskal(Edge[] edges, int n) {
			int minWeight = 0;

			// 按照边权升序
			Arrays.sort(edges, (a, b) -> a.weight - b.weight);

			UnionFindSet ufs = new UnionFindSet(n + 1);

			// 最先遍历出来是边权最小的边
			for (Edge edge : edges) {
				// 如果edge.from节点 和 edge.to节点 是同一个连通分量（即都在最小生成树中），则此时会产生环
				// 因此只有当edge.from节点 和 edge.to节点不在同一个连通分量时，才能合并（纳入最小生成树）
				if (ufs.find(edge.from) != ufs.find(edge.to)) {
					minWeight += edge.weight;
					ufs.union(edge.from, edge.to);

					// 需要注意的是，上面初始化并查集的节点数为n+1个，因此并查集底层fa数组的长度就是n+1，即索引范围是[0, n]，左闭右闭，
					// 其中0索引是无用的，1~n索引对应最小生成树中各个节点，如果者n个节点可以变为最小生成树，那么1~n节点会被合并为一个连通分量
					// 而0索引虽然无用，但是也会自己形成一个连通分量，因此最终如果能形成最小生成树，则并查集中会有两个连通分量
					if (ufs.count == 2) {
						return minWeight;
					}
				}
			}

			return -1;
		}
	}

	// 并查集
	class UnionFindSet {
		int[] fa;
		int count;

		public UnionFindSet(int n) {
			this.fa = new int[n];
			this.count = n;
			for (int i = 0; i < n; i++) this.fa[i] = i;
		}

		public int find(int x) {
			if (x != this.fa[x]) {
				return (this.fa[x] = this.find(this.fa[x]));
			}
			return x;
		}

		public void union(int x, int y) {
			int x_fa = this.find(x);
			int y_fa = this.find(y);

			if (x_fa != y_fa) {
				this.fa[y_fa] = x_fa;
				this.count--;
			}
		}
	}
